hdu 1425 Happy 2004

发表于 | 分类于 ， |

题目链接

hdu 1425 Happy 2004

题解

题目大意:
求

记为$s(2004^x)$

$s(2004^{x})= s(2^2X)) s(3^X) s(167^X)$

$167 \ mod \ 29 = 22 $

$s(2004^X) = s(2^{2X}) s(3^{X})) s(22^X)$
此时底数变为了质数
如果p是素数
$s(p^n)=1+p+p^2+…+p^n= (p^{n+1}-1) / (p-1)$
上面的式子带下来,写代码就好了
对于除法取mod需要求逆元
29为素数->快速幂
或者,打个表不就好了嘛233

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cmath>
#include<cstdio>
#include<algorithm>
inline int read() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
	return x;
}
#define mod 29
int x,a,b,c;
int pow(int a,int p) {
	int ret=1;
	for(;p;p>>=1,a=a*a%mod) {
		if(p&1)ret=ret*a%mod;
	}
	return ret;
}
int main() {
	while(1) {
		x=read();
		if(!x)break;
		a=pow(2,2*x+1);
		b=pow(3,x+1);
		c=pow(22,x+1);
		printf("%d\n",(a-1)*(b-1)*15*(c-1)*18%mod);
	}
	return 0;
}